Lindenmayer Systems

• Lindenmayer systems define a starting string and replacement rules to generate complicated (but somewhat repetitive) strings.
• Example:
  • Start = “A”
  • Rules:
    • “A” \(\to\) “BAC-”
    • “B” \(\to\) “BB-”
    • “C” \(\to\) “CA-”
    • “-” is a constant, so “-” \(\to\) “-”
  • Iterations:
    0. A
    1. BAC-
    2. BB-BAC-CA--
    3. BB-BB--BB-BAC-CA--CA-BAC---
    4. BB-BB--BB-BB---BB-BB--BB-BAC-CA--CA-BAC---CA-BAC--BB-BAC-CA----
• It might help to see the 3rd and 4th iterations spaced out.

B   B   - B   B   -- B   B   - B   A    C   - C   A    -- C   A    - B   A    C   ---
BB- BB- - BB- BB- -- BB- BB- - BB- BAC- CA- - CA- BAC- -- CA- BAC- - BB- BAC- CA- ---

Turtle Graphics

Imagine a turtle dragging a pen across an \((x,y)\) plane. If various characters (letters) in a string represent commands, we can see that L systems lead to fractal-like patterns.

A common set of commands:

• Any uppercase letter between A and L means step forward while drawing.
• Any uppercase letter between M and Z means hop forward without drawing.
• The + symbol means turn clockwise by 90°. (Or some other angle.)
• The - symbol means turn counterclockwise by 90°.
• The [ symbol means to save the current location and direction to the top of a stack of saved positions.
• The ] symbol means to return to most recently saved position, and then remove that position from the stack. (Last in, first out)

So, using our example from the previous page, and starting pointing North (up)…

BB-BB--BB-BB---BB-BB--BB-BAC-CA--CA-BAC---CA-BAC--BB-BAC-CA----

Example 1

Angle = 30°
Start = A
Rules:
  A > A[+A][-A]B
  B > [--B]A
Number of recursions = 7

Example 2

Angle = 60°
Start = A
Rules:
  A > -B+B+B+B+B+B
  B > B[--CCA][-CCA]B
  C > CC
Number of recursions = 7

Example 3

Angle = 45°
Start = A
Rules:
  A > [----AAB][--AAB][++AAB]AAB
  B > [-C][+C][--C][++C][---C][+++C]
  C > CAB
Number of recursions = 6

Example 4

Angle = 72°
Start = A
Rules:
  A > [-AAB][--AAB][+AAB][++AAB]AAB
  B > [-C][+C][--C][++C]CA
  C > CC
Number of recursions = 5

Example 5

Angle = 60°
Start = a
Rules:
  a > -B+B+B+B+B+B
  B > BB[-CCa]
  C > CC
Number of recursions = 9

Example 6

Angle = 72°
Start = A
Rules:
  A > B+B+B+B+B
  B > [-CCA]BB
  C > CC
Number of recursions = 9

Example 7

Angle = 45°
Start = A
Rules:
  A > +A-B-B[B]
  B > -B+A+A[A]
Number of recursions = 8

Example 8

Angle = 90°
Start = A
Rules:
  A > AA[-A][+A]
Number of recursions = 8

Example 9

Angle = 30°
Start = A
Rules:
  A > AcbcA
  b > [+A][-A][++A][--A][+++A][---A][++++A][----A][+++++A][-----A]
  c > bAb
Number of recursions = 6

Example 10

Angle = 30°
Start = AB
Rules:
  A > B--B
  B > AA+++AA
Number of recursions = 12

Example 11

Angle = 30°
Start = x
Rules:
  x > FFF[+FFF+FFF+FF+FF+F+Fx][-FFF-FFF-FF-FF-F-Fx]Fx
  F > FFx
Number of recursions = 6

Example 12

Angle = 45°
Start = A
Rules:
  A > AB
  B > A[++C][--C]
  C > C[+C][-C]A
Number of recursions = 10

Example 13

Angle = 25°
Start = -x
Rules:
  x > F+[[x]-x]-F[-Fx]+x
  F > FF
Number of recursions = 7

Example 14

Angle = 90°
Start = b
Rules:
  A > AA
  b > AbA+AbA+AbA
Number of recursions = 9

Example 15

Angle = 115°
Start = A
Rules:
  A > A+A-A
Number of recursions = 11

Example 16

Angle = 90°
Start = A
Rules:
  A > A[+AA][-AA]B
  B > ABA
Number of recursions = 7

Example 17

Angle = 6°
Start = x
Rules:
  x > FFF[+FF+FF+FF+F+Fx][-FF-FF-FF-F-Fx]FFFFFFFFFFFFFFx
  F > FF
Number of recursions = 8